package com.example.hot100;

/**
 * 给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。
 *  你可以对一个单词进行如下三种操作：
 *  插入一个字符
 *  删除一个字符
 *  替换一个字符
 *
 *  示例 1：
 * 输入：word1 = "horse", word2 = "ros"
 * 输出：3
 * 解释：
 * horse -> rorse (将 'h' 替换为 'r')
 * rorse -> rose (删除 'r')
 * rose -> ros (删除 'e')
 *
 *  示例 2：
 * 输入：word1 = "intention", word2 = "execution"
 * 输出：5
 * 解释：
 * intention -> inention (删除 't')
 * inention -> enention (将 'i' 替换为 'e')
 * enention -> exention (将 'n' 替换为 'x')
 * exention -> exection (将 'n' 替换为 'c')
 * exection -> execution (插入 'u')
 */
public class Leetcode72_MinDistance {
    public static void main(String[] args) {
        String word1= "horse", word2 = "ros";
        System.out.println(new Solution().minDistance(word1, word2));
    }

    static class Solution {
        /**
         * 动态规划
         * 举个例子，word1 = "abcde", word2 = "fgh",算这两字符串的编辑距离，就是找从word1，最少多少步，能变成word2？那就有三种方式：
         *
         *     知道"abcd"变成"fgh"多少步（假设X步），那么从"abcde"到"fgh"就是"abcde"->"abcd"->"fgh"。（一次删除，加X步，总共X+1步）
         *     知道"abcde"变成“fg”多少步（假设Y步），那么从"abcde"到"fgh"就是"abcde"->"fg"->"fgh"。（先Y步，再一次添加，加X步，总共Y+1步）
         *     知道"abcd"变成“fg”多少步（假设Z步），那么从"abcde"到"fgh"就是"abcde"->"fge"->"fgh"。（先不管最后一个字符，把前面的先变好，用了Z步，然后把最后一个字符给替换了。这里如果最后一个字符碰巧就一样，那就不用替换，省了一步）
         * @param word1
         * @param word2
         * @return
         */
        public int minDistance(String word1, String word2) {
            int len1 = word1.length();
            int len2 = word2.length();
            if (len1 * len2 == 0) {// 有一个是空串就返回另一个的长度
                return len1 + len2;
            }
            int[][] dp = new int[len1 + 1][len2 + 1];// dp[i][j] 表示 word1 前 i 个字符组成的子串, 变成word2的前 j 个字符组成的子串所需要的最少转换次数

            // 初始化状态
            for (int i = 0; i <= len1; i++) { // word2 为空串时
                dp[i][0] = i;
            }

            for (int j = 1; j <= len2; j++) {// word1 为空串时
                dp[0][j] = j;
            }

            for (int i = 1; i <= len1; i++) {
                for (int j = 1; j <= len2; j++) {
                    int fromLeft = dp[i - 1][j] + 1;// 可能的情况一
                    int fromDown = dp[i][j - 1] + 1;// 可能的情况二
                    int fromLeftDown = word1.charAt(i - 1) == word2.charAt(j - 1) ?
                            dp[i - 1][j - 1] : dp[i - 1][j - 1] + 1;// 可能的情况三

                    dp[i][j] = Math.min(fromLeft, Math.min(fromDown, fromLeftDown));
                }
            }

            return dp[len1][len2];

        }
    }
}
